Flash memory is one type of non-volatile, rewritable memory commonly used in many types of electronic devices, such as USB drives, digital cameras, mobile phones, and memory cards. Flash memory typically stores information in an array of memory cells made from floating-gate transistors. In traditional single-level cell (SLC) devices, each cell stores only one bit of information. Some newer flash memory, known as multi-level cell (MLC) devices, can store more than one bit per cell by applying multiple levels of electrical charge to the floating gates of memory cells.
A NAND memory is accessed by a host system much like a block device such as a hard disk or a memory card. Typically, the host system performs reads and writes to logical block addresses. A NAND memory is typically divided into blocks and each block is generally organized into pages or sectors of cells. Blocks may be typically 16 KB in size, while pages may be typically 512 or 2,048 or 4,096 bytes in size. Multi-level NAND cells makes management of NAND devices more difficult, particularly in multithreaded real-time run-time environments.
In response, manufacturers have encapsulated NAND flash as memory devices in which a controller is placed in front of a raw NAND memory. The purpose of the controller is to manage the underlying physical characteristics of the NAND memory and to abstract the interface as a logical block device. This allows the NAND memory to provide a logical to physical translation map between logical block addresses (which are being accessed by a host system) and physical locations in the NAND memory, and to manage rules governing the logical to physical translation mapping internally via firmware in a NAND controller.
A translation cache is a type of cache that may be used by managed NAND memories to improve the speed of logical to physical translations. The translation cache has a fixed number of entries that map the logical block addresses onto the physical addresses (e.g., NAND pages). The translation cache can be searched by a requested logical block address and the result is the physical address. If the requested address is present in the translation cache, the search yields a match very quickly, after which the physical address can be used to access the managed NAND memory. If the requested address is not in the translation cache, the translation proceeds by reading translation tables, which contain a larger set of translation entries, and are slower to access.
One problem with respect to the translation process is that the managed NAND memory does not have a global view of the semantics of the logical block accesses, and cannot therefore readily perform any internal optimization. The only information currently transmitted to a managed NAND memory is the logical block being accessed and whether the operation is a read or write. All other context about a particular logical block, both in its relation to other logical blocks and in relation to past and future events is lost.